"""
https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

3. 无重复字符的最长子串
已解答
中等
相关标签
premium lock icon
相关企业
提示
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

 

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

"""

class Solution:
    """
    最暴力的方法，记录开始和结束位置，每次遇到新字符串时，都查看新字符是否在记录范围内。
    不存在则继续，如果存在，则维护新的位置范围。

    时间复杂是O(n^2)

    优化版，是用dict存储指针范围内的字符集合。这样判定时间就是O(1)。
    但难点在于如何从dict中将不需维护的字符排除掉。
    可用dict的key保存字符，val保存索引位置。
    如果待排除的val恰好等于左指针，则仅排除该元素即可。
    如果待排除的val在左右指针范围内，则将左指针到val范围内的所有元素均排除。

    再优化，则可根据size判断是逐个排除还是另起炉灶。

    """
    def lengthOfLongestSubstring(self, s: str) -> int:
        kv:dict[str,int]={}
        left=0
        max_len=0
        for right in range(len(s)):
            new_char=s[right]
            if new_char not in kv:
                kv[new_char]=right
            else:
                max_len=max(max_len,right-left)
                old_idx=kv[new_char]
                for j in range(left,old_idx):
                    del kv[s[j]]
                kv[new_char]=right
                left=old_idx+1
        max_len=max(max_len,len(s)-left)

        return max_len
    
if __name__=='__main__':
    s='dvdf'

    sol=Solution()
    res=sol.lengthOfLongestSubstring(s)
    print(res)